Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World
- Downloads：9817
- Type：Epub+TxT+PDF+Mobi
- Create Date：2021-05-15 08:55:07
- Update Date：2025-09-07
- Status：finish
- Author：Leslie Valiant
- ISBN：0465060722
- Environment：PC/Android/iPhone/iPad/Kindle
- Download
Summary
From a leading computer scientist， a unifying theory that will revolutionize our understanding of how life evolves and learns。
How does life prosper in a complex and erratic world？ While we know that nature follows patterns—such as the law of gravity—our everyday lives are beyond what known science can predict。 We nevertheless muddle through even in the absence of theories of how to act。 But how do we do it？
In Probably Approximately Correct， computer scientist Leslie Valiant presents a masterful synthesis of learning and evolution to show how both individually and collectively we not only survive， but prosper in a world as complex as our own。 The key is “probably approximately correct” algorithms， a concept Valiant developed to explain how effective behavior can be learned。 The model shows that pragmatically coping with a problem can provide a satisfactory solution in the absence of any theory of the problem。 After all， finding a mate does not require a theory of mating。 Valiant’s theory reveals the shared computational nature of evolution and learning， and sheds light on perennial questions such as nature versus nurture and the limits of artificial intelligence。
Offering a powerful and elegant model that encompasses life’s complexity， Probably Approximately Correct has profound implications for how we think about behavior， cognition， biological evolution， and the possibilities and limits of human and machine intelligence。
How does life prosper in a complex and erratic world？ While we know that nature follows patterns—such as the law of gravity—our everyday lives are beyond what known science can predict。 We nevertheless muddle through even in the absence of theories of how to act。 But how do we do it？
In Probably Approximately Correct， computer scientist Leslie Valiant presents a masterful synthesis of learning and evolution to show how both individually and collectively we not only survive， but prosper in a world as complex as our own。 The key is “probably approximately correct” algorithms， a concept Valiant developed to explain how effective behavior can be learned。 The model shows that pragmatically coping with a problem can provide a satisfactory solution in the absence of any theory of the problem。 After all， finding a mate does not require a theory of mating。 Valiant’s theory reveals the shared computational nature of evolution and learning， and sheds light on perennial questions such as nature versus nurture and the limits of artificial intelligence。
Offering a powerful and elegant model that encompasses life’s complexity， Probably Approximately Correct has profound implications for how we think about behavior， cognition， biological evolution， and the possibilities and limits of human and machine intelligence。
Reviews
Arvind
，
Incredibly fascinating to a beginner to evolvable and learnable complexity classes。 I found it a nice bridge to the author's challenging technical work。 Incredibly fascinating to a beginner to evolvable and learnable complexity classes。 I found it a nice bridge to the author's challenging technical work。 。。。more
Mary Keehan
，
The author presents very interesting theories but I found many of the chapters to be extremely dry。 A mathematics enthusiast would likely get more enjoyment out of this one。
Aadesh
，
Enjoyed the concepts of Ecorithms and theoryless。 I really enjoyed the early chapters where the author talks about different complexity class， turing machines and introduces PAC（Proximally Approximate Correct） learning and its two principles。 The way the induction principle works for PAC is elegant。 I found the book verbose in the latter sections。 First few chapters are more informative and interesting that the standard books on theory of computation。
Deniz
，
A popular science book by Leslie Valiant， who developed the Probably Approximately Correct （PAC） Learning framework which was all the rage before neural networks took over Machine Learning， trading high empirical performance for any theoretical guarantees。 This book can be useful as a heady layperson's introduction to theoretical computer science through the development of the PAC framework。 The author also speculates that the theory of evolution can/should be made into more of a theory by havin A popular science book by Leslie Valiant， who developed the Probably Approximately Correct （PAC） Learning framework which was all the rage before neural networks took over Machine Learning， trading high empirical performance for any theoretical guarantees。 This book can be useful as a heady layperson's introduction to theoretical computer science through the development of the PAC framework。 The author also speculates that the theory of evolution can/should be made into more of a theory by having some more predictive power。 I had not thought Darwin's theory of evolution to be lacking until now， so it is refreshing to contemplate cranking up its predictive power and what it would take for this。I found the discussion of two assumptions underlying scientific induction to be interesting。 Namely， The Invariance Assumption: The context in which a generalization is to be applied cannot be fundamentally different from that in which it was made， and the Learnable Regularity Assumption: a little more subtle and concerns feasibility。If you are a computer scientist or are already familiar with PAC learning， much of this book is redundant。 I also found the author to repeat himself in later chapters。 Still， it's worth giving a read。 。。。more
Alessandro Piovaccari
，
A great treatise on learningThis book clearly explain the distinction between theoryful and theoryless problems， and how the latter can be tackled through learning through a novel kind of computation。 Most fascinating is the analysis of the plausibility of the theory of evolution only if inherently funded on the concept of learning itself。
Hdarjus
，
This review has been hidden because it contains spoilers。 To view it， click here。 In general， I missed the Bayesian view from the theory。 In other words， the uncertainty underlying any type of knowledge。 I didn't even finish the book as I was disappointed。 In general， I missed the Bayesian view from the theory。 In other words， the uncertainty underlying any type of knowledge。 I didn't even finish the book as I was disappointed。 。。。more
Jiliac
，
This is an incredible book full of insights。 It explains the basis of the theory that lead the author Turing price。 It presents a more rigorous definition of how algorithms should learn （which he calls ecorithms）。Were it only for me， I would give it five stars because it gave me a lot of food for thoughts。 But considering score as a general recommendation for others， I think the book as two major drawbacks:- The writing is very dry。 Although it's a short book， it takes a lot of focus to read。- I This is an incredible book full of insights。 It explains the basis of the theory that lead the author Turing price。 It presents a more rigorous definition of how algorithms should learn （which he calls ecorithms）。Were it only for me， I would give it five stars because it gave me a lot of food for thoughts。 But considering score as a general recommendation for others， I think the book as two major drawbacks:- The writing is very dry。 Although it's a short book， it takes a lot of focus to read。- It's all very general with very limited application description。 。。。more
Richard
，
An argument that constraints on algorithms are critical in understanding evolution and learning。The book takes us from a discussion of evolution's lack of detail as an algorithm， to discussions on computability （"his [Turing's] importance demands comparison with that of Issac Newton"， p。 28）， polynomial time， P ≠ NP， and the balance between algorithm power and what can be computed （or evolved） in practice and in principle。 A useful introduction to the importants of constraints on algorithms， as An argument that constraints on algorithms are critical in understanding evolution and learning。The book takes us from a discussion of evolution's lack of detail as an algorithm， to discussions on computability （"his [Turing's] importance demands comparison with that of Issac Newton"， p。 28）， polynomial time， P ≠ NP， and the balance between algorithm power and what can be computed （or evolved） in practice and in principle。 A useful introduction to the importants of constraints on algorithms， as provided by the probably approximately correct framework。 There's an interesting balance noted in the book: too expressive an algorithm would not have enough time to produce us; too simple an algorithm might not be able to produce us。The last few chapters of the book contains a grab-bag of big ticket items （conciousness， human congition arising from a simple model） which didn't do it for me。 These topics are too large to be dismissed so quickly。 。。。more
Jina
，
I found this piece very intriguing。 My favourite chapter had to be the one on trying to quantifying human behaviour， particularly the theoretical “mind’s eye” that allows for humans to create an opinion。 The “mind’s eye” acts as a filter between the observed world and what we commit to memory。 Going into this book I had basically no previous knowledge on the development of artificial intelligence。 Movies that depict robots that mimic humans perfectly， seem even more in the realm of “fiction” to I found this piece very intriguing。 My favourite chapter had to be the one on trying to quantifying human behaviour， particularly the theoretical “mind’s eye” that allows for humans to create an opinion。 The “mind’s eye” acts as a filter between the observed world and what we commit to memory。 Going into this book I had basically no previous knowledge on the development of artificial intelligence。 Movies that depict robots that mimic humans perfectly， seem even more in the realm of “fiction” to me now that I have a better understanding as to how that would have to be achieved and the unlikely hood of that happening。 。。。more
Bill Pritchard
，
The score I gave to "Probably Approximately Correct" is more a reflection of my lack of knowledge than the qualities of the book。 There are times when you may be suggested to read a book and find that the material is way "above your paygrade"。 Leslie Valiant is a professor of Computer Science and Applied Mathematics at Harvard。 He is the Nevalinna Prize winner from the International Mathematical Union。 He is obviously extremely qualified to speak of the Probably Approximately Correct Algorithms The score I gave to "Probably Approximately Correct" is more a reflection of my lack of knowledge than the qualities of the book。 There are times when you may be suggested to read a book and find that the material is way "above your paygrade"。 Leslie Valiant is a professor of Computer Science and Applied Mathematics at Harvard。 He is the Nevalinna Prize winner from the International Mathematical Union。 He is obviously extremely qualified to speak of the Probably Approximately Correct Algorithms that he has developed to held how effective behavior can be learned by a computer。 The math in some chapters is necessary but well beyond my aged eyes。。。 my fault - not the authors。 At times the prose sings - and I found myself pulled deeper into the work - but then the math would be rejoined， and I drifted。 If you are in the computer science area， I think this work is a highly suggested read。 But for the rest of us。。。 be prepared to be lost - at least some of the time。 。。。more
Stephen Lee
，
Skip if you are familiar with Computer Science and/or machine learning。 I can't judge how good it is as an introduction to either。 Skip if you are familiar with Computer Science and/or machine learning。 I can't judge how good it is as an introduction to either。 。。。more
Aaron Terrazas
，
Fascinating concept and several interesting parts， but a lot in the weeds。My favorite quote comes early on:"Much of everyday human decision making appears to 。。。 be based on a competent ability to predict from past observation without any good articulation of how the prediction is made or any claim of fundamental understanding of the phenomenon in question。 The predictions need not be perfect or the best possible。 They need merely to be useful enough。" （p 8） Fascinating concept and several interesting parts， but a lot in the weeds。My favorite quote comes early on:"Much of everyday human decision making appears to 。。。 be based on a competent ability to predict from past observation without any good articulation of how the prediction is made or any claim of fundamental understanding of the phenomenon in question。 The predictions need not be perfect or the best possible。 They need merely to be useful enough。" （p 8） 。。。more
Max Shen
，
A challenging read that above all stays faithful to the discipline and integrity of academia to the sacrifice of wider accessibility。 Nevertheless， the ideas are truly thought-provoking， the perspectives and paradigm of thinking quite novel and enlightening， and due to Valiant's ever-present rigor， meaningful and concrete。If you are the type to appreciate an understated yet subtly powerful and rigorously built idea over exaggerated could-be's and fanciful speculations dressed up in scientific wo A challenging read that above all stays faithful to the discipline and integrity of academia to the sacrifice of wider accessibility。 Nevertheless， the ideas are truly thought-provoking， the perspectives and paradigm of thinking quite novel and enlightening， and due to Valiant's ever-present rigor， meaningful and concrete。If you are the type to appreciate an understated yet subtly powerful and rigorously built idea over exaggerated could-be's and fanciful speculations dressed up in scientific wording， you are the perfect audience for this book。To me， this book proves Valiant as a leading thinker in our day and age。 。。。more
Derek Bridge
，
Not an easy read， even for me （and I know something of the underlying theory that he skirts around here）， but thought-provoking in many ways。 Impossible to summarize。
Moses
，
A very excellent exploration of PAC algorithms and their computablity
Michal
，
This book is dense on mathematics， complex conceptually but in all places lucid。 It challenges the reader but offers rewards as well。 The notion of PAC learning applied to evolution in particular is quite interesting。 Approach the book with caution however， it's quite demanding。 This book is dense on mathematics， complex conceptually but in all places lucid。 It challenges the reader but offers rewards as well。 The notion of PAC learning applied to evolution in particular is quite interesting。 Approach the book with caution however， it's quite demanding。 。。。more
Sambasivan
，
The key learning for me is that we do not need to be afraid that computers might take over from humans in future。 Though the so called intelligence and the processing speed of the computers is unbelievably high and growing like never before， they are likely to be subservient to us。 There is a wealth of knowledge and algorithm based theory that is pioneered in this book and though the reading is laboured due to the dry style of writing， one can start understanding the implications if one persists The key learning for me is that we do not need to be afraid that computers might take over from humans in future。 Though the so called intelligence and the processing speed of the computers is unbelievably high and growing like never before， they are likely to be subservient to us。 There is a wealth of knowledge and algorithm based theory that is pioneered in this book and though the reading is laboured due to the dry style of writing， one can start understanding the implications if one persists。 Recommended for computer geeks。 。。。more
Mike
，
Can't give a star rating because I was in so far over my head。 Will put a few definitions down in case I come across them again in reading about machine learning or something related to Alan Turing。 Ecorithm - algorithm that takes information from its environment so as to perform better in that environment。 Algos for machine learning， evolution， and learning for the purpose of reasoning are all examples。 Theoryless - denotes decisions for which there is not a good explanatory and predictive theo Can't give a star rating because I was in so far over my head。 Will put a few definitions down in case I come across them again in reading about machine learning or something related to Alan Turing。 Ecorithm - algorithm that takes information from its environment so as to perform better in that environment。 Algos for machine learning， evolution， and learning for the purpose of reasoning are all examples。 Theoryless - denotes decisions for which there is not a good explanatory and predictive theory， such as a scientific theory。 Probably Approximately Correct learning is learning from examples， "where the number of computational steps is polynomially bounded and errors are polynomially controlled"。 This PAC thesis is the mathematical definition of learning， or generalizing， so that new information can be categorized with a small error rate。 Interesting comment regarding artificial intelligence。 We need not fear intelligent robots - first， because there is no reason to make them exactly like humans。 Second， they will not fear being switched off， unless we provide them with the same heritage of extreme survival training that our own ancestors had been subject to on Earth。 "I believe the attempt to make a thinking machine will help us greatly in finding out how we think ourselves。" Alan Turing"When seeking to understand the fundamental character of life， learning algorithms are a good place to start。" 。。。more
Timothy Corbett-Clark
，
Disappointing following a really interesting start。
Doug
，
A fascinating call to action about trying to explain the gaps in the theory of evolution with computer algorithms。 It is illuminating as to the gaps in evolution， which are ignored by some quarters， and exploited by others for an explanation by magical forces。 It is not a clarion call to the mystical， but it is admirably humble about the subject of the "theoryless" aspects of evolution and intelligence。 It contains an interesting twist through some computer science concepts which will be unfamil A fascinating call to action about trying to explain the gaps in the theory of evolution with computer algorithms。 It is illuminating as to the gaps in evolution， which are ignored by some quarters， and exploited by others for an explanation by magical forces。 It is not a clarion call to the mystical， but it is admirably humble about the subject of the "theoryless" aspects of evolution and intelligence。 It contains an interesting twist through some computer science concepts which will be unfamiliar to some readers， but of interest to me having studied some of them in school。 I think even if you skim through the science and math there enough meat left on the bones for anyone。 For me， this is the first step into a new realm。 。。。more
Cloudbuster
，
Computer Science is no more about computers than astronomy is about telescopes。Nell’accezione comune l’informatica è vista solo come quella tecnologia che permette di scrivere documenti， preparare presentazioni， ritoccare foto e spedirle in tempo reale in giro per il mondo。 In realtà， l’informatica è una scienza （non a caso， in inglese è denominata computer science） e probabilmente negli ultimi 50 anni è stata la più prolifica delle scienze e quella che ha fornito i maggiori contributi allo svil Computer Science is no more about computers than astronomy is about telescopes。Nell’accezione comune l’informatica è vista solo come quella tecnologia che permette di scrivere documenti， preparare presentazioni， ritoccare foto e spedirle in tempo reale in giro per il mondo。 In realtà， l’informatica è una scienza （non a caso， in inglese è denominata computer science） e probabilmente negli ultimi 50 anni è stata la più prolifica delle scienze e quella che ha fornito i maggiori contributi allo sviluppo delle conoscenze umane。 I numi tutelari di questa nuova scienza sono senz’altro Alan Turing e John Von Neumann ma， in questi anni， un drappello di menti brillanti， se non geniali， ha raccolto il loro testimone ed ha contribuito a fornire un modello matematico rigoroso della computazione che si è rivelato utile a tutti gli altri settori della conoscenza umana， dalla fisica alla biologia， dall’economia alle scienze cognitive。Leslie Valiant rientra a pieno titolo in questa ristretta cerchia di grandi menti della computer science。 Un uomo geniale e visionario， che con le sue ricerche ha aperto nuovi campi come quello del machine learning， una delle aree fondamentali dell'intelligenza artificiale che si occupa della realizzazione di sistemi e algoritmi che si basano su osservazioni come dati per la sintesi di nuova conoscenza。In questo piccolo， ma molto ambizioso， libro Valiant descrive la sua visione della realtà e propone una teoria matematica， sufficientemente semplice ed elegante， che possa spiegare tutti i meccanismi essenziali che governano il comportamento degli esseri viventi: l’adattamento， l’evoluzione， l’apprendimento， la ragione， la conoscenza。 Il suo modello è basato sull’idea degli ecoritmi， algoritmi che sono "con alta probabilità approssimativamente corretti" e che imparano dall’interazione con il loro ambiente。 Valiant analizza potenza e limiti degli ecoritmi e mostra come siano applicabili alla conoscenza umana， alla biologia evolutiva ed all’intelligenza artificiale。Il libro non è di facile lettura ma è assolutamente illuminante ed è un “must” per tutti coloro che sono interessati a capire come funziona la nostra mente ed il mondo che ci circonda。 。。。more
Alexander Leo Swenson
，
Wonderfully dry prose that sandwiches some mindblowing ideas to the uninitiated。 Anyone who shares Chomsky's crabbiness about the rise of probabilistic models should read this as a detente for theoryful/theoryless science and our impending theoryful/theoryless world。 Wonderfully dry prose that sandwiches some mindblowing ideas to the uninitiated。 Anyone who shares Chomsky's crabbiness about the rise of probabilistic models should read this as a detente for theoryful/theoryless science and our impending theoryful/theoryless world。 。。。more
David Wiley
，
If you're interested in how people learn， you will definitely enjoy this book。 It presents an interesting view on learning and how it emerges from interactions with the environment。 There's a lot in this book to appreciate in terms of developing a better understanding of learning。 I found myself agreeing frequently - but not always - with the author。 If you're interested in how people learn， you will definitely enjoy this book。 It presents an interesting view on learning and how it emerges from interactions with the environment。 There's a lot in this book to appreciate in terms of developing a better understanding of learning。 I found myself agreeing frequently - but not always - with the author。 。。。more
Faust Mephisto
，
The writing is a bit dry but overall an informative book。 It touches on some very interesting issues， like the Bayesian statistical component of evolution and the associated questions of evolutionary learning and memory。
Mills College Library
，
150。1 V172 2013
Alexandrea
，
This book is interesting if you have at least some background in computer science and discrete math/logic， and a basic understanding of the theory of evolution。 Be warned that it mostly reads like a doctoral thesis - don't expect a ton of watered-down explanations or definitions for the general reader。 This book is interesting if you have at least some background in computer science and discrete math/logic， and a basic understanding of the theory of evolution。 Be warned that it mostly reads like a doctoral thesis - don't expect a ton of watered-down explanations or definitions for the general reader。 。。。more
Alexi Parizeau
，
Excellently written with a passion for the subject that's contagious （at least to me！）。 I'd say for a general audience it would also be considered easy to understand since it had little in terms of technical distractions。 There was also enough in the Notes section to get me started on the key breakthroughs in Learning Theory。[First Reading: April 5-6， 2015] Excellently written with a passion for the subject that's contagious （at least to me！）。 I'd say for a general audience it would also be considered easy to understand since it had little in terms of technical distractions。 There was also enough in the Notes section to get me started on the key breakthroughs in Learning Theory。[First Reading: April 5-6， 2015] 。。。more
Suhrob
，
I was surprised to see a non-technical book on such a rather arcane and technical subject （though with rich implications in many areas）。The book gives a decent low-tech introduction to PAC learning， but if I have to make one complaint Leslie Valiant is not really an engaging writer （or a writer not interested in being engaging） - his examples and approach is extremely dry （you know drawing balls from urns etc。）He even manages to introduce the perceptron in the most boring manner。 I'd say it is a I was surprised to see a non-technical book on such a rather arcane and technical subject （though with rich implications in many areas）。The book gives a decent low-tech introduction to PAC learning， but if I have to make one complaint Leslie Valiant is not really an engaging writer （or a writer not interested in being engaging） - his examples and approach is extremely dry （you know drawing balls from urns etc。）He even manages to introduce the perceptron in the most boring manner。 I'd say it is a science writer dream - "look a simple algo inspired by the neurons in your very brain， how exciting！" etc。 - but no， he gives a vague top level unexciting description and goes to linearly separable problems。。。 oh well a chance missed :） It is not that he refuses to talk down to the reader （because the book is really low on technicality）， it just like he is not that keen on talking to you all that much。 Who knows how this book deal came to be。。。 In any case I give 4 stars because the topic is so interesting and fertile。 More technical readers might be better served by a shorter review paper though。 。。。more
Hollis Fishelson-holstine
，
Recommended by C， but not in lib
Stefan
，